using System;
using System.Collections;

namespace Slaks.Graphs.Algorithms
{
	public class MaxCommonSubGraphVertexEdgeCount
	{
		/// <summary>
		/// Get the common graph between two graphs (Max common)
		/// </summary>
		/// <param name="one"></param>
		/// <param name="two"></param>
		/// <returns></returns>
		public static Graph GetMCS(Graph one, Graph two)
		{
			one.SortVertices();
			two.SortVertices();

			Graph result = new Graph();

			VertexList oneList = one.GetVertexList();
			VertexList twoList = two.GetVertexList();

			int compare;

			#region find vertices

			//find intersections
			int i = 0, j = 0;
			while (i < oneList.Count && j < twoList.Count)
			{
				compare = oneList[i].CompareTo(twoList[j]);
				if (compare < 0) i++;
				else if (compare == 0)
				{
					result.CreateAddVertex(oneList[i].GetId());
					i++;
					j++;
				}
				else j++;
			}

			#endregion

			#region find edges

			VertexList resultList = result.GetVertexList();
			if (resultList.Count <= 1) return result;

			Vertex vertexOne;
			Vertex vertexTwo;

			Vertex vertexOneNext;
			Vertex vertexTwoNext;

			long id;
			long nextId;
			IDictionary sectionsOne, sectionsTwo;
			for (i = 0; i < resultList.Count; i++)
			{
				id = resultList[i].GetId();
				vertexOne = one.GetVertex(id);
				vertexTwo = two.GetVertex(id);

				for (j = i; j < resultList.Count; j++)
				{
					nextId = resultList[j].GetId();
					sectionsOne = vertexOne.GetSectionsIfConnected(nextId);
					sectionsTwo = vertexTwo.GetSectionsIfConnected(nextId);

					ICollection sectionsOneKeys = sectionsOne.Keys;

					foreach (string section in sectionsOneKeys)
					{
						if (sectionsTwo.Contains(section))
						{
							resultList[i].AddEdge(resultList[j], section);
						}
					}

					if (id == nextId) continue;
					vertexOneNext = one.GetVertex(nextId);
					vertexTwoNext = two.GetVertex(nextId);

					sectionsOne = vertexOneNext.GetSectionsIfConnected(id);
					sectionsTwo = vertexTwoNext.GetSectionsIfConnected(id);

					sectionsOneKeys = sectionsOne.Keys;
					foreach (string section in sectionsOneKeys)
					{
						if (sectionsTwo.Contains(section))
						{
							resultList[j].AddEdge(resultList[i], section);
						}
					}

				} //end of for
			}

			#endregion

			return result;
		}


		public static Graph GetSlaksMCS(Graph one, Graph two)
		{
			Graph result = GetMCS(one, two);

			#region find additiona edges

			VertexList resultList = result.GetVertexList();
			if (resultList.Count <= 1) return result;

			Vertex vertexOne;
			Vertex vertexTwo;

			Vertex vertexOneNext;
			Vertex vertexTwoNext;

			long id;
			long nextId;
			IDictionary sectionsOne, sectionsTwo, sectionsResult;
			IList commonSection = new ArrayList();
			for (int i = 0; i < resultList.Count; i++)
			{
				id = resultList[i].GetId();
				vertexOne = one.GetVertex(id);
				vertexTwo = two.GetVertex(id);

				for (int j = i + 1; j < resultList.Count; j++)
				{
					nextId = resultList[j].GetId();

					#region

					/*
					sectionsOne = vertexOne.GetSectionsIfConnected(nextId);
					sectionsTwo = vertexTwo.GetSectionsIfConnected(nextId);

					ICollection sectionsOneKeys = sectionsOne.Keys;

					foreach (string section in sectionsOneKeys)
					{
						if (sectionsTwo.Contains(section))
						{
							resultList[i].AddEdge(resultList[j], section);
						}
					}

					if (id == nextId) continue;
					vertexOneNext = one.GetVertex(nextId);
					vertexTwoNext = two.GetVertex(nextId);

					sectionsOne = vertexOneNext.GetSectionsIfConnected(id);
					sectionsTwo = vertexTwoNext.GetSectionsIfConnected(id);

					sectionsOneKeys = sectionsOne.Keys;
					foreach (string section in sectionsOneKeys)
					{
						if (sectionsTwo.Contains(section))
						{
							resultList[j].AddEdge(resultList[i], section);
						}
					}*/

					#endregion

					sectionsOne = vertexOne.GetSectionsIfConnected(nextId);

					vertexTwoNext = two.GetVertex(nextId);
					sectionsTwo = vertexTwoNext.GetSectionsIfConnected(id);


					foreach (string section1 in sectionsOne.Keys)
					{
						if (sectionsTwo.Contains(section1) == true) commonSection.Add(section1);
					}

					sectionsResult = resultList[i].GetSectionsIfConnected(nextId);

					//add connection to result if edge with connection does not exists
					foreach (string section in commonSection)
					{
						if (sectionsResult.Contains(section) == false) resultList[i].AddEdge(resultList[j], section);
					}

					commonSection.Clear();

				} //end of for
			}

			#endregion

			return result;
		}
	}

	/// <summary>
	/// Get common subgraph for such representations as RawFrequency and NormalizedFrequency
	/// </summary>
	public class MaxCommonSubGraphVertexEdgeFrequency
	{
		public static Graph GetMCS(Graph one, Graph two)
		{
			one.SortVertices();
			two.SortVertices();

			Graph result = new Graph();

			VertexList oneList = one.GetVertexList();
			VertexList twoList = two.GetVertexList();

			int compare;

			#region find vertices

			//find intersections
			int i = 0, j = 0;
			while (i < oneList.Count && j < twoList.Count)
			{
				compare = oneList[i].CompareTo(twoList[j]);
				if (compare < 0) i++;
				else if (compare == 0)
				{
					result.CreateAddVertex(oneList[i].GetId()).Frequency = Math.Min(oneList[i].Frequency, twoList[j].Frequency);
					i++;
					j++;
				}
				else j++;
			}

			#endregion

			#region find edges

			VertexList resultList = result.GetVertexList();
			if (resultList.Count <= 1) return result;

			Vertex vertexOne;
			Vertex vertexTwo;

			Vertex vertexOneNext;
			Vertex vertexTwoNext;

			long id;
			long nextId;
			IDictionary sectionsOne, sectionsTwo;

			double edgeFrequencyOne;
			double edgeFrequencyTwo;
			for (i = 0; i < resultList.Count; i++)
			{
				id = resultList[i].GetId();
				vertexOne = one.GetVertex(id);
				vertexTwo = two.GetVertex(id);

				for (j = i; j < resultList.Count; j++)
				{
					nextId = resultList[j].GetId();
					sectionsOne = vertexOne.GetSectionsIfConnected(nextId);
					sectionsTwo = vertexTwo.GetSectionsIfConnected(nextId);

					ICollection sectionsOneKeys = sectionsOne.Keys;

					foreach (string section in sectionsOneKeys)
					{
						if (sectionsTwo.Contains(section))
						{
							edgeFrequencyOne = vertexOne.GetEdgeFrequency(nextId, section);
							edgeFrequencyTwo = vertexTwo.GetEdgeFrequency(nextId, section);
							resultList[i].AddEdge(resultList[j], section).SetFrequency(Math.Min(edgeFrequencyOne, edgeFrequencyTwo));
						}
					}

					if (id == nextId) continue;
					vertexOneNext = one.GetVertex(nextId);
					vertexTwoNext = two.GetVertex(nextId);

					sectionsOne = vertexOneNext.GetSectionsIfConnected(id);
					sectionsTwo = vertexTwoNext.GetSectionsIfConnected(id);

					sectionsOneKeys = sectionsOne.Keys;
					foreach (string section in sectionsOneKeys)
					{
						if (sectionsTwo.Contains(section))
						{
							edgeFrequencyOne = vertexOneNext.GetEdgeFrequency(id, section);
							edgeFrequencyTwo = vertexTwoNext.GetEdgeFrequency(id, section);

							resultList[j].AddEdge(resultList[i], section).SetFrequency(Math.Min(edgeFrequencyOne, edgeFrequencyTwo));
						}
					}

				} //end of for
			}

			#endregion

			return result;
		}
	}
}